package Top_Interview_Questions.Union_Find;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/8 12:06
 * <p>
 * 功能描述:
 */
public class _0128 {

    public static void main(String[] args) {
        _0128 test = new _0128();
        int[] nums = {100, 4, 200, 1, 3, 2};
        test.longestConsecutive(nums);
    }


    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        for (int num : num_set) {
            //2-1=1,1在序列中,说明2这个数字一定出现在其他的连续序列中。
            if (!num_set.contains(num-1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum+1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }


}
